package code;

import java.util.Stack;


public class LargestRectangle {

	static public class Node{
		int value;
		int l;
		int r;
		Node(int val){
			value=val;
		}
	}
	
	private int n;
	private Node[] nodes;
	
	public void initTree(){
//		nodes=new Node[8*n];
		/*
		 * 上面创建对象数组是不对的，在运行的时候，如果使用它的话，会抛出运行的NULLPoint错误
		 * PS：这点与基本类型数组创建不太一样。可以通过手动的创建每个对象
		 */
		nodes=new Node[4*n];
		for(int i=0;i<4*n;i++)
			nodes[i]=new Node(Integer.MAX_VALUE);
		buildTree(1,0,n-1);
	}
	
	public void buildTree(int idx,int l,int r){
		System.out.println(idx+" "+l+" "+r);
		if(l==r){
			nodes[idx].l=l;
			nodes[idx].r=r;
			return;
		}
		int mid=l+r>>1;
		buildTree(2*idx,l,mid);
		buildTree(2*idx+1,mid+1,r);
		nodes[idx].l=nodes[2*idx].l;
		nodes[idx].r=nodes[2*idx+1].r;
	}
	public void insert(int idx,int pidx,int val){
		if(nodes[idx].l==pidx && nodes[idx].l==nodes[idx].r){
			nodes[idx].value=val;
			return;
		}
		int mid=nodes[idx].l+nodes[idx].r>>1;
		if(pidx<=mid){
			insert(2*idx,pidx,val);
		}
		else{
			insert(2*idx+1,pidx,val);
		}
		nodes[idx].value=min(nodes[2*idx].value,nodes[2*idx+1].value);
	}
	
	public int query(int idx,int l,int r){
		if(nodes[idx].l==l && nodes[idx].r==r)
			return nodes[idx].value;
		int mid=nodes[idx].l+nodes[idx].r>>1;
		if(r<=mid){
			return query(2*idx,l,r);
		}
		else if(l>mid){
			return query(2*idx+1,l,r);
		}
		else{
			int a=query(2*idx,l,mid);
			int b=query(2*idx+1,mid+1,r);
			return min(a,b);
		}
	}
	public int min(int a,int b){
		return a>b?b:a;
	}
    public int largestRectangleArea(int[] height) {
    	int i,j;
    	n=height.length;
    	if(n==0) return 0;
    	initTree();
    	for(i=0;i<n;i++){
    		insert(1,i,height[i]);
    	}
    	int maxArea=0;
    	for(i=0;i<n;i++){
    		for(j=0;j<=i;j++){
    			int minLen=query(1,j,i);
    			if(maxArea<minLen*(i-j+1)){
    				maxArea=minLen*(i-j+1);
    			}
    		}
    	}
        return maxArea;
    }
	
    public int largestRectangleAreaII(int[] height){
    	int i;
    	Stack<Integer> stack=new Stack<Integer>();
    	int n=height.length;
    	if(n==0)	return 0;
    	int maxArea=0;
    	i=0;
    	while(i<n || !stack.empty()){
    		if(stack.empty() || i<n && height[i]>=height[stack.peek()]){
    			stack.push(i++);
    		}
    		else{
    			int t=stack.peek();
    			stack.pop();
    			maxArea=max(maxArea,height[t]*(i-t));
    		}
    		System.out.println(i+"  "+maxArea);
    	}
    	return maxArea;
    }
    
    public int max(int a,int b){
    	return a>b?a:b;
    }
    
    public boolean isPalindrome(int x) {
    	String s=Integer.toString(x);
    	for(int i=0;i<s.length()/2;i++){
    		if(s.charAt(i)!=s.charAt(s.length()-1-i))
    			return false;
    	}
        return true;
    }
    
    public void setZeroes(int[][] matrix) {
        int i,j;
        int n=matrix.length;
        int m=matrix[0].length;
        
        boolean[] row=new boolean[n];
        boolean[] col=new boolean[m];
        
        for(i=0;i<n;i++)
        	for(j=0;j<m;j++){
        		if(matrix[i][j]==0){
        			row[i]=true;
        			col[j]=true;
        		}
        	}
    	 for(i=0;i<n;i++){
    		 if(row[i]){
    			 for(j=0;j<m;j++)
    	         		matrix[i][j]=0;
    		 }
    	 }
    	 for(i=0;i<m;i++){
    		 if(col[i]){
    			 for(j=0;j<n;j++)
    	         		matrix[j][i]=0;
    		 }
    	 }
    }
	public static void main(String[] args){
		LargestRectangle lr=new LargestRectangle();
		int[] height={2,1,5,6,2,3};
//		int[] height={2};
		System.out.println(lr.largestRectangleAreaII(height));
		
	}
}
